#include <vector>
#include <climits>

// 时间复杂度O(MAX(N+range))
// 空间复杂度O(range)
// 稳定性：稳定

static void countSort(std::vector<int> &nums)
{
    int max = INT_MIN, min = INT_MAX;
    for (auto &x : nums)
    {
        if (x > max)
            max = x;
        if (x < min)
            min = x;
    }

    int range = max - min + 1;
    std::vector<int> Count(range);
    for (auto &x : nums)
    {
        Count[x - min]++;
    }

    int i = 0;
    for (int j = 0; j < range; j++)
    {
        while (Count[j]--)
        {
            nums[i++] = j + min;
        }
    }
}